package com.cat.DataStructure04;

import java.util.Arrays;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/replace-words/
 * @create 2025/11/26 10:08
 * @since JDK17
 */

public class Solution13 {
    static int MAXN = ((int) 1e5), cnt;
    static int[][] tree = new int[MAXN][26];
    static int[] end = new int[MAXN];
    static void insert(String word) {
        int cur = 1;
        for (int i = 0, path; i < word.length(); i++) {
            path = word.charAt(i) - 'a';
            if (tree[cur][path] == 0) {
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path] = ++cnt;
        }
        end[cur]++;
    }
    static String search(String word) {
        int cur = 1;
        for (int i = 0, path; i < word.length(); i++) {
            path = word.charAt(i) - 'a';
            if (tree[cur][path] == 0) { // 断了
                return word;
            }
            if (end[cur] != 0) {    //
                return word.substring(0, i + 1);
            }
            cur = tree[cur][path];
        }
        return word;
    }

    public String replaceWords(List<String> dictionary, String sentence) {
        cnt = 1;
        for (var x : dictionary) {
            insert(x);
        }
        String[] s = sentence.split(" ");
        for (int i = 0; i < s.length; i++) {
            s[i] = search(s[i]);
        }
        Arrays.fill(end, 1, cnt + 1, 0);
        StringBuilder ans = new StringBuilder();
        for (var x : s) {
            ans.append(x);
        }
        ans.delete(ans.length() - 1, ans.length());
        return ans.toString();
    }
}
